// 1.二分查找非递归
function binary(arr, target) {
    let low = 0
    let high = arr.length - 1
    while (low <= high) {
        let mid = Math.floor((low + high) / 2)
        if (arr[mid] === target) {
            return mid
        } else if (arr[mid] > target) {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return -1
}

// 2.二分查找递归方式
function recursion(arr, low, high, target) {
    if (low > high) return -1
    let mid = Math.floor((low + high) / 2)
    if (arr[mid] === target) {
        return mid
    } else if (arr[mid] > target) {
        return recursion(arr, low, mid - 1)
    } else {
        return recursion(arr, mid + 1, high)
    }
}


// 二分查找非递归
let array = [2, 3, 5, 12, 22, 34, 35, 67]
console.log(binary(array, 12));
// 二分查找非递归
let arr = [2, 3, 5, 12, 22, 34, 35, 67]
console.log(recursion(arr, 0, arr.length - 1, 112));
